package org.trc.network;

import java.util.ArrayList;
import java.util.Collection;
import java.util.Collections;
import java.util.Iterator;
import java.util.List;

import org.trc.network.Edge;
import org.trc.network.Node;

/**
 * Represents a walk in a graph.
 * 
 * A walk W is defined as an ordered set of  nodes that two adjacenct nodes in the set share an edge. 
 *  
 * @author Justin Deoliveira, Refractions Research Inc, jdeolive@refractions.net
 * 
 */

public class Path extends ArrayList<Object> {
	private static final long serialVersionUID = 1L;
	
	private List m_edges;

	public Path() {
		
	}

	@SuppressWarnings("unchecked")
	public Path(Collection<?> nodes) {
		super(nodes);
	}

	public boolean isValid() {
		return (getEdges() != null);
	}

	/**
	 * 
	 * @return The edges of the walk, otherwise null if the edges cannot be calculated.
	 * 
	 */
	public List<?> getEdges() {
		if (m_edges == null) {
			m_edges = buildEdges();
		}
		return (m_edges);
	}
	
	/**
	 * Adds a node to the walk. Adding a node clears the edge list which will be
	 * recalculated on the next call to getEdges().
	 * 
	 * @param node
	 *            Node to add to the walk.
	 */
	public boolean add(Node node) {
		m_edges = null;
		return (super.add(node));
	}

	public void add(int index, Object element) {
		super.add(index, element);
		m_edges = null;
	}

	public boolean add(Object o) {
		return (add((Node) o));
	}

	public boolean addAll(Collection c) {
		m_edges = null;
		return (super.addAll(c));
	}

	public boolean addAll(int index, Collection c) {
		m_edges = null;
		return (super.addAll(index, c));
	}

	/**
	 * append edge to end of path, path must be empty, or last node in path must be a node of the edge
	 * 
	 * @param e
	 * @return
	 */
	/*
	public boolean addEdge(Edge e) {
		// save current edge list
		List edges = getEdges();
		if (isEmpty()) {// add both nodes
//			add(e.getNodeA());
//			add(e.getNodeB());
		} else {
			// walk is not empty, check to see if the last node is related to the edge
			Node last = getLast();
//			if (last.equals(e.getNodeA())) {
//				add(e.getNodeB());
//			} else if (last.equals(e.getNodeB())) {
//				add(e.getNodeA());
//			} else
//				return (false);
		}
		// the addition of nodes resets the internal edge list so it must be
		// rebuilt.
		// In the case that an edge shares both of its nodes with another edge
		// it is possible for the list to be rebuilt properly (ie. not contain
		// the edge being added). To rectify this situation, a backup copy of
		// the edge list is saved before the addition, the addition performed, the
		// edge explicitly added to the backup edge list, and the internal
		// edge list replaced by the modified backup 
		edges.add(e);
		m_edges = edges;
		return (true);
	}

	public void addEdges(Collection edges) {
		for (Iterator itr = edges.iterator(); itr.hasNext();) {
			Edge e = (Edge) itr.next();
			addEdge(e);
		}
	}

    */
	
	/**
	 * Removes a node from the walk. Removing a node clears the edge list which
	 * will be recalculated on the next call to getEdges().
	 * 
	 * @param node
	 *            Node to remove from the walk.
	 */
	public void remove(Node node) {
		super.remove(node);
		m_edges = null;
	}

	public Object remove(int index) {
		m_edges = null;
		return (super.remove(index));
	}

	public boolean remove(Object o) {
		m_edges = null;
		return (super.remove(o));
	}

	public boolean removeAll(Collection c) {
		m_edges = null;
		return (super.removeAll(c));
	}

	/**
	 * Determines if the walk is closed. A closed walk is one in which the first
	 * and last nodes are the same.
	 * 
	 * @return True if closed, otherwise false.
	 */
	public boolean isClosed() {
		if (isEmpty() || !isValid())
			return (false);
		return (get(0).equals(get(size() - 1)));
	}

	/**
	 * @see NodeSequence#getFirst()
	 */
	public Node getFirst() {
		return ((Node) get(0));
	}

	/**
	 * @see NodeSequence#getLast()
	 */
	public Node getLast() {
		return ((Node) get(size() - 1));
	}

	/**
	 * Internal method for building the edge set of the walk. This method
	 * calculated the edges upon every call.
	 * 
	 * @return The list of edges for the walk, or null if the edge set could not
	 *         be calculated due to an invalid walk.
	 */
	protected List buildEdges() {
		
		ArrayList edges = new ArrayList();
		
		for (int i = 1; i < size(); i++) {
			Node pre = (Node) get(i - 1);
			Node cur = (Node) get(i);
			
			//modified by linxu as following
			String edgeID = pre.getEdge(cur.id);
			
			if(edgeID != null)
				edges.add(edgeID);
			else
				return null;}

		return (edges);
	}

	/**
	 * Reverses the path.
	 */
	public void reverse() {
		Collections.reverse(this);
		m_edges = null;
	}

	/**
	 * Truncates the path at the specified index. Nodes in the path whose index
	 * is >= the specified index are removed.
	 * 
	 * @param The index of first node to be removed.
	 */
	public void truncate(int index) {
		removeRange(index, size());
		m_edges = null;
	}

	/**
	 * Returns an iterator that iterates over the path in reverse. The iterator
	 * does not support the remove operation.
	 * 
	 * @return the reverse iterator.
	 */
	public Iterator<?> riterator() {
		return (new Iterator<Object>() {
			int m_index = size() - 1;

			public void remove() {
				throw new UnsupportedOperationException(
						"Path iterator does not support remove()");
			}

			public boolean hasNext() {
				return (m_index > -1);
			}

			public Object next() {
				return (get(m_index--));
			}
		});
	}

	public Path duplicate() {
		return (new Path(this));
	}

	public boolean equals(Object other) {
		if (other instanceof Path)
			return (equals((Path) other));
		return (false);
	}

	public boolean equals(Path other) {
		if (other.size() == size()) {
			// make a node by node comparision
			Iterator<?> thisnodes = iterator();
			Iterator<?> othernodes = other.iterator();

			while (thisnodes.hasNext()) {
				Node thisnode = (Node) thisnodes.next();
				Node othernode = (Node) othernodes.next();

				if (!thisnode.equals(othernode))
					return (false);
			}
			return (true);
		}
		return (false);
	}

	public int hashCode() {
		int hash = 7;
		hash = 31 * hash + getFirst().hashCode();
		hash = 31 * hash + getLast().hashCode();
		return (hash);
	}

}

